package com.lw.leetcode.add.e;

/**
 * Created with IntelliJ IDEA.
 * 887. 鸡蛋掉落
 *
 * @author liw
 * @version 1.0
 * @date 2022/8/11 9:18
 */
public class SuperEggDrop {

    public static void main(String[] args) {
        SuperEggDrop test = new SuperEggDrop();

//        int k = 2;
//        int n = 100;

        // 2
//        int k = 1;
//        int n = 2;

        // 3
//        int k = 2;
//        int n = 6;


        // 4
//        int k = 3;
//        int n = 14;

        // 4
        int k = 2;
        int n = 100;

        int i = test.superEggDrop(k, n);
        System.out.println(i);
        System.out.println(test.t);

    }

    private int[] arr;
    private int c;

    private long t = 0;
    public int superEggDrop(int k, int n) {
        this.c = n;
        this.arr = new int[k * n + 1];
        for (int i = 0; i <= n; i++) {
            arr[i] = i;
        }
        return find(k, n);
    }

    private int find(int k, int n) {
        int m = (k - 1) * c + n;
        if (arr[m] != 0) {
            return arr[m];
        }
        if (n == 1) {
            arr[m] = 1;
            return 1;
        }
        int max = n ;
        for (int i = 2; i < n; i++) {
            t++;
            int f = (k - 2) * c + i - 1;
            int a = arr[f];
            if (arr[f] == 0) {
                a = find(k - 1, i - 1);
                arr[f]= a;
            }
            f = (k - 1) * c + n - i;
            int b = arr[f];
            if (arr[f] == 0) {
                a = find(k, n - i);
                arr[f]= a;
            }
            max = Math.min(max, Math.max(a, b) + 1);
        }
        arr[m] = max;
        return max;
    }

}
